package system2021.src.class29manacher;

public class Code01_Manacher {

    public static int manacher2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // 获取新串
        char[] arr = getManacher(s);
        int N = arr.length;
        // 每个下标对应的回文串半径，这里的半径是包含下标本身
        int[] radius = new int[N];
        // 当前最右回文区域下标
        int R = -1;
        // 和R对应的C的下标
        int C = -1;
        // 结果
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            // 以C为中心的镜像下标
            int preIndex = C - (i - C);
            // 1. i超过最右边回文区域的话，那么直接暴力扩
            // 2. i没有超过右边回文区域的话，先更新半径，通过半径来判断是否进行扩
            radius[i] = i >= R ? 1 : Math.min(radius[preIndex], R - i + 1);
            while (i + radius[i] > R && i + radius[i] < N && i - radius[i] >= 0) {
                // 遇到相同进行扩，不同直接跳出
                if (arr[i + radius[i]] == arr[i - radius[i]]) {
                    C = i;
                    R++;
                    radius[i]++;
                } else {
                    break;
                }
            }
            max = Math.max(max, radius[i]);
        }
        return max - 1;
    }

    public static int manacher(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // "12132" -> "#1#2#1#3#2#"
        char[] str = manacherString(s);
        // 回文半径的大小
        int[] pArr = new int[str.length];
        int C = -1;
        // 讲述中：R代表最右的扩成功的位置。coding：最右的扩成功位置的，再下一个位置
        int R = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < str.length; i++) {
            // R第一个违规的位置，i>= R
            // i位置扩出来的答案，i位置扩的区域，至少是多大。
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]])
                    pArr[i]++;
                else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }

    private static char[] getManacher(String s) {
        StringBuilder builder = new StringBuilder();
        builder.append("#");
        for (int i = 0; i < s.length(); i++) {
            builder.append(s.charAt(i)).append("#");
        }
        return builder.toString().toCharArray();
    }

    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    // for test
    public static int right(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = manacherString(s);
        int max = 0;
        for (int i = 0; i < str.length; i++) {
            int L = i - 1;
            int R = i + 1;
            while (L >= 0 && R < str.length && str[L] == str[R]) {
                L--;
                R++;
            }
            max = Math.max(max, R - L - 1);
        }
        return max / 2;
    }

    // for test
    public static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            if (manacher(str) != right(str)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }

}
